package org.leetcode1000;

/**
 * @Auther: qingle
 * @Date: 2024/9/15-0:17
 * @Description:
 *
 * KMP算法的核心思想：
 * 部分匹配表（Partial Match Table）：在开始搜索之前，KMP算法会构建一个部分匹配表（也称为“前缀函数”或“最长公共前缀后缀表”），这个表用于存储模式字符串（子串）中每个位置的前缀和后缀的最长公共元素长度。这个表帮助算法在不匹配时知道应该将模式字符串移动多远。
 *
 * 模式字符串的移动：在搜索过程中，当遇到不匹配的字符时，KMP算法会利用部分匹配表来决定模式字符串应该向右移动多远，而不是简单地将模式字符串向右移动一位。
 *
 * >>TODO
 * 实际编程中，KMP算法可以用来高效地解决字符串匹配问题，即在一个大的文本字符串中搜索一个模式字符串的出现。以下是使用KMP算法解决该问题的步骤：
 *
 * 1. 预处理模式字符串
 * 首先，你需要构建模式字符串的部分匹配表（也称为前缀函数或LPS表）。这个表用于存储模式字符串中每个前缀的最长可匹配后缀的长度。
 *
 * 2. 搜索过程
 * 使用部分匹配表来指导搜索过程。从文本字符串的起始位置开始，将模式字符串与文本字符串进行比较。如果字符匹配，继续比较下一个字符；如果字符不匹配，利用部分匹配表来决定模式字符串应该向右移动多远。
 *
 * 4. 优化和注意事项
 * 预处理：部分匹配表的构建是KMP算法的关键预处理步骤，它需要在搜索之前完成。
 * 边界情况：在实现时要注意处理文本字符串和模式字符串的边界情况。
 * 性能：KMP算法的时间复杂度为O(n + m)，其中n是文本字符串的长度，m是模式字符串的长度。这比简单的暴力搜索方法更高效。
 *
 *
 * @version: 1.0
 */
public class L001_KMP {

		// 构建部分匹配表（LPS表）
		public int[] computeLPSArray(String pattern) {
			int[] lps = new int[pattern.length()];
			int length = 0; // 最长公共前后缀的长度
			int i = 1;
			lps[0] = 0; // lps[0]总是0
			while (i < pattern.length()) {
				if (pattern.charAt(i) == pattern.charAt(length)) {
					length++;
					lps[i] = length;
					i++;
				} else {
					if (length != 0) {
						length = lps[length - 1];
						// 注意，我们在这里不增加i
					} else {
						lps[i] = 0;
						i++;
					}
				}
			}
			return lps;
		}

		// KMP搜索算法
		public void KMPSearch(String text, String pattern) {
			int[] lps = computeLPSArray(pattern);
			int i = 0; // text的索引
			int j = 0; // pattern的索引
			while (i < text.length()) {
				if (pattern.charAt(j) == text.charAt(i)) {
					i++;
					j++;
				}
				if (j == pattern.length()) {
					System.out.println("Found pattern at index " + (i - j));
					j = lps[j - 1];
				} else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {
					if (j != 0) {
						j = lps[j - 1];
					} else {
						i++;
					}
				}
			}
		}

		public static void main(String[] args) {
			String text = "ABABDABACDABABCABAB";
			String pattern = "ABABCABAB";
			L001_KMP kmp = new L001_KMP();
			kmp.KMPSearch(text, pattern);
		}
	}